Hilbert Projection Theorem

Let HH be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and MM be a finite dimensioal subspace of HH. Then for any x∈Hx \in H, there exists a unique y∈My \in M such that

min⁡m∈M∥x−m∥\min_{m \in M} \|x-m\|

has a unique solution yy. In other words "we can find a unique point in MM that is closest to xx". If m∗m^* is the closest point to xx in MM, then x−m∗⊥Mx-m^* \perp M.

Proof: See lecture notes.

Remark: The proof stated that m∗=x1m^* = x_1 is the closest point to MM. It can also be interpreted as the best approximation of xx choosen from the vectors in MM. The x2x_2 term is the error in the approximation.

Example: Let V=R2V=\mathbb{R}^2 and M=span{[1,1]T}M = \text{span}\{[1,1]^T\}. Find the best approximation of x=[4,7]Tx=[4,7]^T in MM.

Solution: We need to find m∗m^* such that m∗=α[11]m^* = \alpha \begin{bmatrix} 1 \\ 1 \end{bmatrix} and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  <x−m∗,m>=0∀m∈M(x-m^*) \perp M \implies <x-m^*, m> = 0 \quad \forall m \in M
<x−m∗,[11]>=0<x-m^*, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Replace x and m∗ with their values.\text{Replace $x$ and $m^*$ with their values.}
<[4−α7−α],[11]>=0<\begin{bmatrix} 4-\alpha \\ 7-\alpha \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
4−α+7−α=04-\alpha + 7-\alpha = 0
α=112\alpha = \frac{11}{2}
m∗=112[11]m^* = \frac{11}{2} \begin{bmatrix} 1 \\ 1 \end{bmatrix}

Example: Let x∈Vx \in V and M=span{v1,v2}M = \text{span}\{v_1, v_2\}. Find the best approximation of xx in MM.

Solution: We need to find m∗m^* such that m∗=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2 that is in the span of MM and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  (x−m∗)⊥both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
<x−α1v1−α2v2,v1>=<x,v1>−α1<v1,v1>−α2<v2,v1>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_1> = <x, v_1> - \alpha_1 <v_1, v_1> - \alpha_2 <v_2, v_1> = 0
<x−α1v1−α2v2,v2>=<x,v2>−α1<v1,v2>−α2<v2,v2>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_2> = <x, v_2> - \alpha_1 <v_1, v_2> - \alpha_2 <v_2, v_2> = 0
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
[α1α2]=[<v1,v1><v2,v1><v1,v2><v2,v2>]−1[<x,v1><x,v2>]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix}^{-1} \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
m∗=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2

Example: Let V=R3V = \mathbb{R}^3 and M=span{[1,1,1]T,[1,0,1]T}M = \text{span}\{[1,1,1]^T, [1,0,1]^T\}. Find the best approximation of x=[4,7,2]Tx=[4,7,2]^T in MM.

Solution: We need to find m∗m^* such that m∗=α1[111]+α2[101]m^* = \alpha_1 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \alpha_2 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} that is in the span of MM and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  (x−m∗)⊥both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
[3222][α1α2]=[136]\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[3222]−1[136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[1−1−13/2][136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -1 & 3/2 \end{bmatrix} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[7−4]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix}
m∗=α1v1+α2v2=7[111]−4[101]=[373]m^* = \alpha_1 v_1 + \alpha_2 v_2 = 7 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 3 \end{bmatrix}

Example: Let HH be the space of square integrable functions on [−π,π][-\pi , \pi ] with inner product <f,g>=∫−ππf(t)g(t)ˉdt<f,g> = \int_{-\pi}^{\pi} f(t)\bar{g(t)}dt. Let MM be the subspace of HH, M=span{ejkt/2π}M = \text{span}\{e^{jkt}/\sqrt{2\pi}\}, k from −N to Nk \text{ from } -N \text{ to } N. Note that dimension of MM is 2N+12N+1.

<fn,fm>=∫−ππejnt2πe−jmt2πdt=12π∫−ππej(n−m)tdt<f_n, f_m> = \int_{-\pi}^{\pi} \frac{e^{jnt}}{\sqrt{2\pi}} \frac{e^{-jmt}}{\sqrt{2\pi}} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt
If n≠m, then 12π∫−ππej(n−m)tdt=12πej(n−m)tj(n−m)∣−ππ=0\text{If $n \neq m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \frac{e^{j(n-m)t}}{j(n-m)} \Big|_{-\pi}^{\pi} = 0
If n=m, then 12π∫−ππej(n−m)tdt=12π∫−ππ1dt=1\text{If $n = m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} 1 dt = 1
Therefore, <fn,fm>={1if n=m0if n≠m\text{Therefore, } <f_n, f_m> = \begin{cases} 1 & \text{if $n = m$} \\ 0 & \text{if $n \neq m$} \end{cases}

Now, let g∈Hg \in H be an arbitrary function. Then g=g1+g2g = g_1 + g_2 where g1∈Mg_1 \in M and g2∈M⊥g_2 \in M^{\perp}. We need to find g1g_1 such that ∥g−g1∥\|g-g_1\| is minimum.

g1=∑k=−NNαkejkt2π where αk=<g,fk>=∫−ππg(t)e−jkt2πdt g_1 = \sum_{k=-N}^{N} \alpha_k \frac{e^{jkt}}{\sqrt{2\pi}} \text{ where } \alpha_k = <g, f_k> = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
αk=∫−ππg(t)e−jkt2πdt \alpha_k = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
g1=∑k=−NN∫−ππg(t)e−jkt2πejkt2πdt=∑k=−NN∫−ππg(t)12πdt=∫−ππg(t)dt g_1 = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} \frac{e^{jkt}}{\sqrt{2\pi}} dt = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{1}{2\pi} dt = \int_{-\pi}^{\pi} g(t) dt

Example: Find the orthagonal projection of the vector [100]\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} onto the subspace M=span{[111],[1−11]}M = \text{span}\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\}.

Solution: We know that the projection matrix is P=B(BTB)−1BTP = B(B^TB)^{-1}B^T where BB is the matrix whose columns are the basis vectors of MM. Therefore,

B=[111−111]B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}
BTB=[3113]B^TB = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}
P=[111−111][3113]−1[1111−11]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[111−111][3/8−1/8−1/83/8][1111−11]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3/8 & -1/8 \\ -1/8 & 3/8 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[1/201/20101/201/2]P = \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}
P[100]=[1/201/2]P \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

Solution of Linear Equations

Consider the linear equation expressed as

Ax=b where A∈Cm×n,x∈Cn,b∈CmAx = b \text{ where } A \in \mathbb{C}^{m \times n}, x \in \mathbb{C}^n, b \in \mathbb{C}^m

If m=nm = n, then the equation has a unique solution. If m<nm < n, then the equation has infinitely many solutions. If m>nm > n, then the equation has no solution.

Example: Let A=[1111]A = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and b=[2.21.92.11.8]b = \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

b∈?range(A) b \in^{?} \text{range}(A)
range(A)=span{[1,1,1,1]T}\text{range}(A) = \text{span}\{[1,1,1,1]^T\}
span{[1,1,1,1]T}={[a,a,a,a]T∣a∈R}\text{span}\{[1,1,1,1]^T\} = \{[a,a,a,a]^T \mid a \in \mathbb{R}\}
b∉range(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

Lets call this best approximation b∗b^*. Then, b∗=α[1111]b^* = \alpha \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and ∥Ax−b∗∥2\|Ax-b^*\|^2 is minimum.

B=[1111]B = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}
P=[1111][4]−1[1111]P = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}
Pb=[1111][4]−1[1111][2.21.92.11.8]Pb = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}
Pb=b∗=[2.02.02.02.0]Pb = b^* = \begin{bmatrix} 2.0 \\ 2.0 \\ 2.0 \\ 2.0 \end{bmatrix}

Example: Let A=[21212121]A = \begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} and b=[l1l2l3l4]b = \begin{bmatrix} l_1 \\ l_2 \\ l_3 \\ l_4 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution: Now, the rows of AA are linearly dependent. Therefore, AA is not full rank. Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

b∗=[lˉlˉlˉlˉ] where lˉ=l1+l2+l3+l44b^* = \begin{bmatrix} \bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix} \text{ where } \bar l = \frac{l_1+l_2+l_3+l_4}{4}
[21212121][x1x2]=[lˉlˉlˉlˉ]\begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix}\bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix}
[x1x2]=[lˉ−lˉ] is any solution, more examples [1−1],[2−3],[3−5],…\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} \text{ is any solution, more examples } \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \begin{bmatrix} 2 \\ -3 \end{bmatrix}, \begin{bmatrix} 3 \\ -5 \end{bmatrix}, \ldots
A minimum norm solution is can be found by minimizing the norm of x.\text{A minimum norm solution is can be found by minimizing the norm of $x$.}
 For that, we can project any solution onto the null space perpendicular to A.\text{ For that, we can project any solution onto the null space perpendicular to $A$.}
x1=ProjN(A)⊥[lˉ−lˉ]x_1 = \text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Corollary: N(A)⊥=range(A∗)\text{Corollary: } N(A)^{\perp} = \text{range}(A^*)
A∗=[22221111]A^* = \begin{bmatrix} 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 1 \end{bmatrix}
range(A∗)=span{[21]}\text{range}(A^*) = \text{span}\bigg \{\begin{bmatrix} 2 \\ 1 \end{bmatrix}\bigg\}
ProjN(A)⊥[lˉ−lˉ]=Projrange(A∗)[lˉ−lˉ]\text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Projrange(A∗)[lˉ−lˉ]=<[lˉ−lˉ],[21]><[21],[21]>[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{<\begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>}{<\begin{bmatrix} 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
Projrange(A∗)[lˉ−lˉ]=lˉ5[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{\bar l}{5} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
 Or in projection matrix form, Q=[21] then, P=Q(Q∗Q)−1Q∗\text{ Or in projection matrix form, } Q = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \text{ then, } P = Q(Q^*Q)^{-1}Q^*
P=[21]15[21]=[4/52/52/51/5]P = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \frac{1}{5} \begin{bmatrix} 2 & 1 \end{bmatrix} = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix}
x1=Px=[4/52/52/51/5][lˉ−lˉ]=[4/5lˉ−2/5lˉ2/5lˉ−1/5lˉ]=[2/5lˉ1/5lˉ]=lˉ/5[21]x_1 = Px = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \begin{bmatrix} 4/5 \bar l - 2/5 \bar l \\ 2/5 \bar l - 1/5 \bar l \end{bmatrix} = \begin{bmatrix} 2/5 \bar l \\ 1/5 \bar l \end{bmatrix} = \bar l/ 5 \begin{bmatrix} 2 \\ 1 \end{bmatrix}

#EE501 - Linear Systems Theory at METU